package chapter04_RecursionAndDynamic;

/**
 * 描述：表达式得到期望结果的总数
 *
 * @author hl
 * @date 2021/7/16 21:07
 */
public class ExpectExpressionNum {

    public static void main(String[] args) {
        String express = "1^0|0|1";
        boolean desired = false;
        ExpectExpressionNum expectExpressionNum = new ExpectExpressionNum();
        int num = expectExpressionNum.num1(express, desired);
        int num2 = expectExpressionNum.num2(express, desired);
        System.out.println(num);
        System.out.println(num2);
    }

    /**
     * 动态规划
     *
     *      要求出任意两个位置i，j之间的表达式的组合数
     * @param express
     * @param desired
     * @return
     */
    public int num2(String express, boolean desired){
        if (!isValid(express)) {
            return 0;
        }
        int n = express.length();
        int[][] t = new int[n][n];//记录i，j的下标的表达式为true的种数
        int[][] f = new int[n][n];//记录i，j的下标的表达式为false的种数
        //初始化
        t[0][0] = express.charAt(0) == '1' ? 1 : 0;
        f[0][0] = express.charAt(0) == '1' ? 0 : 1;
        for (int i = 2; i < n; i += 2) {
            t[i][i] = express.charAt(0) == '1' ? 1 : 0;
            f[i][i] = express.charAt(0) == '1' ? 0 : 1;
            for (int j = i - 2; j >= 0; j -= 2) {
                for (int k = j; k < i; k += 2) {
                    if (express.charAt(k + 1) == '&') {
                        t[j][i] += t[j][k] * t[k + 2][i];
                        f[j][i] += (f[j][k] + t[j][k]) * f[k + 2][i] + f[j][k] * t[k + 2][i];
                    }else if (express.charAt(k + 1) == '|') {
                        t[j][i] += (f[j][k] + t[j][k]) * t[k + 2][i] + t[j][k] * f[k + 2][i];
                        f[j][i] += f[j][k] * f[k + 2][i];
                    }else{
                        t[j][i] += f[j][k] * t[j][k] + t[j][k] * f[k + 2][i];
                        f[j][i] += f[j][k] * f[k + 2][i] + t[j][k] * t[k + 2][i];
                    }
                }
            }
        }
        return desired ? t[0][n - 1] : f[0][n - 1];
    }

    /**
     * 暴力递归，时间复杂度为O(N!)，额外空间复杂度为O(N)
     * @param express
     * @param desired
     * @return
     */
    public int num1(String express, boolean desired){
        if (!isValid(express)) {
            return 0;
        }
        return process(express, desired, 0, express.length() - 1);
    }

    private int process(String express, boolean desired, int l, int r) {
        if (l >= r) {
            return express.charAt(l) == '1' ^ desired ? 0 : 1;
        }
        int num = 0;
        char ch;
        for (int i = l + 1; i < r; i += 2) {
            ch = express.charAt(i);
            if (ch == '^') {
                num += desired ? process(express, true, l, i - 1) * process(express, false, i + 1, r)
                        + process(express, false, l, i - 1) * process(express, true, i + 1, r)
                        : process(express, true, l, i - 1) * process(express, true, i + 1, r)
                        + process(express, false, l, i - 1) * process(express, false, i + 1, r);
            }else if (ch == '&') {
                num += desired ? process(express, true, l, i - 1) * process(express, true, i + 1, r)
                        : process(express, true, l, i - 1) * process(express, false, i + 1, r)
                        + process(express, false, l, i - 1) * process(express, true, i + 1, r);
            }else {
                num +=  desired ? process(express, true, l, i - 1) * process(express, true, i + 1, r)
                        + process(express, true, l, i - 1) * process(express, false, i + 1, r)
                        + process(express, false, l, i - 1) * process(express, true, i + 1, r)
                        : process(express, false, l, i - 1) * process(express, false, i + 1, r);
            }
        }
        return num;
    }

    private boolean isValid(String express) {
        if (express == null || express.length() == 0 || express.length() % 2 == 0) {
            return false;
        }
        char ch ;
        for (int i = 0; i < express.length(); i++) {
            ch = express.charAt(i);
            if (i % 2 == 0) {
                if (ch != '1' && ch != '0') {
                    return false;
                }
            }else{
                if (ch != '&' && ch != '|' && ch != '^') {
                    return false;
                }
            }
        }
        return true;
    }

}
